package com.codebuffer.nowcoder;

import java.util.Arrays;

public class reConstructBinaryTree {

    public static void main(String[] args) {
        int a [][] = {{1,2,3,4,5,6,7},{3,2,4,1,6,5,7}};
        reConstructBinaryTree(a[0],a[1]);
    }
    public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {

        if(pre.length==0|| in.length==0){
            return null;
        }
//        1,2,3,4,      5,6,7
//        3,2,4,1,      6,5,7
        TreeNode treeNode = new TreeNode(pre[0]);
        for (int i = 0; i < in.length; i++) {
            if(in[i]==pre[0]){
                treeNode.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                treeNode.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
            }
        }

        return treeNode;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }


}
/**
 if (pre.length == 0 || in.length == 0) {
 return null;
 }
 TreeNode root = new TreeNode(pre[0]);
 // 在中序中找到前序的根
 for (int i = 0; i < in.length; i++) {
 if (in[i] == pre[0]) {
 // 左子树，注意 copyOfRange 函数，左闭右开
 root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
 // 右子树，注意 copyOfRange 函数，左闭右开
 root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
 break;
 }
 }
 return root;
 **/